﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;

namespace iNet.Cache
{
	/// <summary>
	/// 使用 Least Recently Used (LRU) 演算法的物件快取容器。
	/// </summary>
	/// <typeparam name="TKey">物件辨識的型別。</typeparam>
	/// <typeparam name="TValue">物件型別。</typeparam>
	public class ObjectCache<TKey, TValue> : IDictionary<TKey, TValue>
	{
		#region CacheEntry
		class CacheEntry<TKey, TValue>
		{
			public TKey Key;
			public readonly LinkedListNode<CacheEntry<TKey, TValue>> UsageListNode;
			public TValue Value;

			public CacheEntry(TKey key, TValue value)
			{
				this.UsageListNode = new LinkedListNode<CacheEntry<TKey, TValue>>(this);
				this.Key = key;
				this.Value = value;
			}
		}
		#endregion
		#region ValueEnumerator
		class ValueEnumerator<TKey, TValue> : IEnumerator<TValue>
		{
			#region 欄位
			readonly IEnumerator<CacheEntry<TKey, TValue>> _EntryEnumerator;
			#endregion
			#region 建構子
			public ValueEnumerator(IEnumerator<CacheEntry<TKey, TValue>> entryEnumerator)
			{
				_EntryEnumerator = entryEnumerator;
			}
			#endregion
			#region Current
			public TValue Current
			{
				get 
				{
					CacheEntry<TKey, TValue> entry = _EntryEnumerator.Current;
					return (entry != null ? entry.Value : default(TValue));
				}
			}
			#endregion
			#region Dispose
			public void Dispose()
			{
				_EntryEnumerator.Dispose();
			}
			#endregion
			#region IEnumerator.Current
			object IEnumerator.Current
			{
				get 
				{
					return this.Current;
				}
			}
			#endregion
			#region MoveNext
			public bool MoveNext()
			{
				return _EntryEnumerator.MoveNext();
			}
			#endregion
			#region Reset
			public void Reset()
			{
				_EntryEnumerator.Reset();
			}
			#endregion
		}
		#endregion
		#region 欄位
		int _Capacity;
		readonly Dictionary<TKey, CacheEntry<TKey, TValue>> _Entries;
		readonly LinkedList<CacheEntry<TKey, TValue>> _EntryPool = new LinkedList<CacheEntry<TKey, TValue>>();
		readonly LinkedList<CacheEntry<TKey, TValue>> _UsageList = new LinkedList<CacheEntry<TKey, TValue>>();
		#endregion
		#region 建構子
		/// <summary>
		/// 初始化新的 ObjectCache 執行個體，並將快取容量初始化為 1024。
		/// </summary>
		public ObjectCache()
			: this(1024, null)
		{ }
		/// <summary>
		/// 初始化新的 ObjectCache 執行個體。
		/// </summary>
		/// <param name="capacity">快取容量。</param>
		/// <exception cref="ArgumentOutOfRangeException">capacity 小於或等於零。</exception>
		public ObjectCache(int capacity)
			: this(capacity, null)
		{ }
		/// <summary>
		/// 初始化新的 ObjectCache 執行個體，並將快取容量初始化為 1024。
		/// </summary>
		/// <param name="comparer">物件辨識的相等比較介面。</param>
		public ObjectCache(IEqualityComparer<TKey> comparer)
			: this(1024, comparer)
		{ }
		/// <summary>
		/// 初始化新的 ObjectCache 執行個體。
		/// </summary>
		/// <param name="capacity">快取容量。</param>
		/// <param name="comparer">物件辨識的相等比較介面。</param>
		/// <exception cref="ArgumentOutOfRangeException">capacity 小於或等於零。</exception>
		public ObjectCache(int capacity, IEqualityComparer<TKey> comparer)
		{
			//確認參數
			if (capacity <= 0)
				throw new ArgumentOutOfRangeException();

			//初始化
			_Capacity = capacity;
			_Entries = new Dictionary<TKey, CacheEntry<TKey, TValue>>(comparer);
		}
		#endregion
		#region Add
		/// <summary>
		/// 將新的物件加入至快取中。
		/// </summary>
		/// <param name="key">物件識別。</param>
		/// <param name="value">物件。</param>
		[MethodImpl(MethodImplOptions.Synchronized)]
		public void Add(TKey key, TValue value)
		{
			//確認物件是否已存在
			CacheEntry<TKey, TValue> entry;
			if (_Entries.TryGetValue(key, out entry))
			{
				_UsageList.Remove(entry.UsageListNode);
				_UsageList.AddFirst(entry.UsageListNode);
				return;
			}

			//加入至快取
			if (_EntryPool.Count > 0)
			{
				entry = _EntryPool.First.Value;
				entry.Key = key;
				entry.Value = value;
				_EntryPool.RemoveFirst();
			}
			else
				entry = new CacheEntry<TKey, TValue>(key, value);
			_Entries[key] = entry;
			_UsageList.AddFirst(entry.UsageListNode);
			this.EnsureCapacity();
		}
		#endregion
		#region Capacity
		/// <summary>
		/// 取得或設定快取物件的個數上限。
		/// </summary>
		public int Capacity
		{
			get
			{
				return _Capacity;
			}
			[MethodImpl(MethodImplOptions.Synchronized)]
			set
			{
				if (_Capacity != value)
				{
					if (value <= 0)
						throw new ArgumentOutOfRangeException();
					_Capacity = value;
					this.EnsureCapacity();
				}
			}
		}
		#endregion
		#region Clear
		/// <summary>
		/// 清除所有快取的物件。
		/// </summary>
		[MethodImpl(MethodImplOptions.Synchronized)]
		public void Clear()
		{
			_Entries.Clear();
			LinkedListNode<CacheEntry<TKey, TValue>> node = _UsageList.First;
			while (node != null)
			{
				LinkedListNode<CacheEntry<TKey, TValue>> nextNode = node.Next;
				CacheEntry<TKey, TValue> entry = node.Value;
				entry.Key = default(TKey);
				entry.Value = default(TValue);
				_UsageList.Remove(node);
				if (_EntryPool.Count <= _Capacity)
					_EntryPool.AddFirst(node);
				node = nextNode;
			}
		}
		#endregion
		#region Contains
		/// <summary>
		/// 確認指定的物件是否已快取。
		/// </summary>
		/// <param name="key">物件識別。</param>
		/// <returns>True 表示物件已快取，False 表示沒有。</returns>
		[MethodImpl(MethodImplOptions.Synchronized)]
		public bool Contains(TKey key)
		{
			return _Entries.ContainsKey(key);
		}
		#endregion
		#region Count
		/// <summary>
		/// 取得已快取的物件個數。
		/// </summary>
		public int Count
		{
			get 
			{
				return _Entries.Count;
			}
		}
		#endregion
		#region EnsureCapacity
		void EnsureCapacity()
		{
			while (_UsageList.Count > _Capacity)
			{
				CacheEntry<TKey, TValue> entry = _UsageList.Last.Value;
				_Entries.Remove(entry.Key);
				TKey key = entry.Key;
				TValue value = entry.Value;
				entry.Key = default(TKey);
				entry.Value = default(TValue);
				_UsageList.RemoveLast();
				_EntryPool.AddFirst(entry.UsageListNode);
				this.OnObjectRemoved(key, value);
			}
			while (_EntryPool.Count > _Capacity + 1)
				_EntryPool.RemoveFirst();
		}
		#endregion
		#region GetEnumerator
		/// <summary>
		/// 取得用來列舉已快取物件的 IEnumerator&lt;TValue&gt; 介面。
		/// </summary>
		/// <returns>IEnumerator&lt;TValue&gt; 介面。</returns>
		public IEnumerator<TValue> GetEnumerator()
		{
			return new ValueEnumerator<TKey, TValue>(_Entries.Values.GetEnumerator());
		}
		#endregion
		#region ICollection<KeyValuePair<TKey, TValue>>.Add
		void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
		{
			this.Add(item.Key, item.Value);
		}
		#endregion
		#region ICollection<KeyValuePair<TKey, TValue>>.Contains
		[MethodImpl(MethodImplOptions.Synchronized)]
		bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
		{
			//取得快取資訊
			CacheEntry<TKey, TValue> entry;
			if (!_Entries.TryGetValue(item.Key, out entry))
				return false;

			//比對物件
			if (entry.Value != null)
				return entry.Value.Equals(item.Value);
			return (item.Value == null);
		}
		#endregion
		#region ICollection<KeyValuePair<TKey, TValue>>.CopyTo
		[MethodImpl(MethodImplOptions.Synchronized)]
		void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
		{
			//確認參數
			if (array == null)
				throw new ArgumentNullException("array");
			if (arrayIndex < 0 || (arrayIndex + _Entries.Count) > array.Length)
				throw new ArgumentOutOfRangeException();

			//複製物件
			foreach (CacheEntry<TKey, TValue> entry in _Entries.Values)
				array[arrayIndex++] = new KeyValuePair<TKey, TValue>(entry.Key, entry.Value);
		}
		#endregion
		#region ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
		bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
		{
			get
			{
				return false;
			}
		}
		#endregion
		#region ICollection<KeyValuePair<TKey, TValue>>.Remove
		[MethodImpl(MethodImplOptions.Synchronized)]
		bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
		{
			if (!(this as IDictionary<TKey, TValue>).Contains(item))
				return false;
			return this.Remove(item.Key);
		}
		#endregion
		#region IDictionary<TKey, TValue>.ContainsKey
		bool IDictionary<TKey, TValue>.ContainsKey(TKey key)
		{
			return this.Contains(key);
		}
		#endregion
		#region IDictionary<TKey, TValue>.Keys
		ICollection<TKey> IDictionary<TKey, TValue>.Keys
		{
			get 
			{
				return _Entries.Keys;
			}
		}
		#endregion
		#region IDictionary<TKey, TValue>.this[TKey key]
		TValue IDictionary<TKey, TValue>.this[TKey key]
		{
			get
			{
				return this[key];
			}
			set
			{
				throw new NotSupportedException();
			}
		}
		#endregion
		#region IDictionary<TKey, TValue>.Values
		ICollection<TValue> IDictionary<TKey, TValue>.Values
		{
			[MethodImpl(MethodImplOptions.Synchronized)]
			get
			{
				TValue[] values = new TValue[_Entries.Count];
				int i = 0;
				foreach (CacheEntry<TKey, TValue> entry in _Entries.Values)
					values[i++] = entry.Value;
				return values;
			}
		}
		#endregion
		#region IEnumerable.GetEnumerator
		IEnumerator IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}
		#endregion
		#region IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator
		IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
		{
			throw new NotSupportedException();
		}
		#endregion
		#region OnObjectRemoved
		/// <summary>
		/// 將物件從快取中移除後所呼叫的內部方法。
		/// </summary>
		/// <param name="key">移除的物件識別。</param>
		/// <param name="value">移除的物件。</param>
		protected virtual void OnObjectRemoved(TKey key, TValue value)
		{ }
        #endregion
		#region Remove
		/// <summary>
		/// 將指定的物件從快取中移除。
		/// </summary>
		/// <param name="key">物件識別。</param>
		/// <returns>True 表示移除成功，False 表示失敗。</returns>
		[MethodImpl(MethodImplOptions.Synchronized)]
		public bool Remove(TKey key)
		{
			//取得快取資訊
			CacheEntry<TKey, TValue> entry;
			if (!_Entries.TryGetValue(key, out entry))
				return false;

			//移除快取
			_Entries.Remove(key);
			_UsageList.Remove(entry.UsageListNode);
			entry.Key = default(TKey);
			entry.Value = default(TValue);
			if (_EntryPool.Count <= _Capacity)
				_EntryPool.AddFirst(entry.UsageListNode);
			return true;
		}
		#endregion
		#region this[key]
		/// <summary>
		/// 從快取中取得指定的物件。
		/// </summary>
		/// <param name="key">物件識別。</param>
		/// <returns>從快取中取出的物件。</returns>
		public TValue this[TKey key]
		{
			[MethodImpl(MethodImplOptions.Synchronized)]
			get
			{
				TValue value;
				this.TryGetValue(key, out value);
				return value;
			}
		}
		#endregion
		#region TryGetValue
		/// <summary>
		/// 嘗試從快取中取得指定的物件。
		/// </summary>
		/// <param name="key">物件識別。</param>
		/// <param name="value">從快取中取出的物件。</param>
		/// <returns>True 表示物件存在於快取中，False 表示不存在。</returns>
		[MethodImpl(MethodImplOptions.Synchronized)]
		public bool TryGetValue(TKey key, out TValue value)
		{
			//取得快取資訊
			CacheEntry<TKey, TValue> entry;
			if (!_Entries.TryGetValue(key, out entry))
			{
				value = default(TValue);
				return false;
			}

			//更新快取資訊
			_UsageList.Remove(entry.UsageListNode);
			_UsageList.AddFirst(entry.UsageListNode);
			value = entry.Value;
			return true;
		}
		#endregion
	}
}
